package Algorithm.backTracking;

import java.util.*;

/**
 * 46. 全排列 https://leetcode.cn/problems/permutations
 * 题目简述：给定一个不含重复数字的数组nums ，返回其所有可能的全排列。
 */
public class Permute {

    public static void main(String[] args) {
        new Permute().permute(new int[]{1,2,3});
    }

    /**
     * 思路：回溯算法。在路径选择列表剪枝时，组合问题可进行顺序性剪枝，而排列问题只能剪去path已使用过的数据
     * 用一个布尔数组标记每个数是否使用过，回溯时删除路径并将对应元素使用标记重置为false
     * 回溯递归函数参数：（结果集，已选择路径，数组nums和已使用标记used构成的下一步路径选择列表）
     * 回溯递归函数体：1.路径长度已达到要求，则加入结果集然后return
     *              2.遍历当前选择列表：将选择加入路径，然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        backTracking(result, path, nums, used);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        //路径选择列表：[0, n-1]
        for(int i=0;i < nums.length;i++) {
            //可行性剪枝：已使用数据（即path中已有）略过
            if (!used[i]) {
                //添加到路径
                path.add(nums[i]);
                used[i] = true;
                //*递归下一步选择列表
                backTracking(result, path, nums, used);
                //回溯撤销上一步选择，继续遍历同层其他选择
                path.removeLast();
                used[i] = false;
            }
        }
    }
}
